class Solution
{
public:
    int longestStrChain(vector<string> &words)
    {
        sort(words.begin(), words.end(), [&](auto &s1, auto &s2)
             { return s1.size() < s2.size(); });
        int n = words.size();
        vector<int> maxChainDp(n, 1);
        int maxChainLen = 1;
        int newSizeStart = 0;
        // int lastNewSizeStart = 0;
        for (int i = 1; i < n; ++i)
        {
            if (words[i].size() != words[newSizeStart].size())
            {
                // lastNewSizeStart = newSizeStart;
                newSizeStart = i;
            }
            for (int j = newSizeStart - 1; j >= 0; --j)
            {
                int sizeDiff = words[i].size() - words[j].size();
                if (sizeDiff != 1)
                {
                    break;
                }
                else
                {
                    if (isPredecessor(words[j], words[i]))
                    {
                        maxChainDp[i] = max(maxChainDp[i], 1 + maxChainDp[j]);
                        maxChainLen = max(maxChainLen, maxChainDp[i]);
                    }
                }
            }
        }
        return maxChainLen;
    }

    bool isPredecessor(string &s1, string &s2)
    {
        int n = s1.size();
        int added = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s1[i] != s2[i + added])
            {
                if (added == 0)
                {
                    added = 1;
                    --i;
                }
                else
                {
                    return false;
                }
            }
        }
        return true;
    }
};